package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-11 01:31
 **/
public class LeetCode911 {

    List<Integer> tops;
    Map<Integer, Integer> voteCounts;
    int[] times;

    public LeetCode911(int[] persons, int[] times) {
        tops = new ArrayList<>();
        voteCounts = new HashMap<>();
        voteCounts.put(-1, -1);
        int top = -1;
        for (int i = 0; i < persons.length; ++i) {
            int p = persons[i];
            voteCounts.put(p, voteCounts.getOrDefault(p, 0) + 1);
            if (voteCounts.get(p) >= voteCounts.get(top)) {
                top = p;
            }
            tops.add(top);
        }
        this.times = times;
    }

    public int q(int t) {
        int l = 0, r = times.length - 1;
        // 找到满足 times[l] <= t 的最大的 l
        while (l < r) {
            int m = l + r + 1 >> 1;
            if (times[m] <= t) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        return tops.get(l);
    }

    public static void main(String[] args) {
        LeetCode911 code = new LeetCode911(new int[]{0, 1, 1, 0, 0, 1, 0}, new int[]{0, 5, 10, 15, 20, 25, 30});
        System.out.println("code.q(3) = " + code.q(3));
        System.out.println("code.q(12) = " + code.q(12));
        System.out.println("code.q(25) = " + code.q(25));
        System.out.println("code.q(15) = " + code.q(15));
        System.out.println("code.q(24) = " + code.q(24));
        System.out.println("code.q(8) = " + code.q(8));
    }

}
